/*
 * @Author: szx
 * @Date: 2021-10-24 12:45:47
 * @LastEditTime: 2021-10-24 13:52:16
 * @Description:
 * @FilePath: \leetcode\638\638.go
 */
package main

func shoppingOffers(price []int, special [][]int, needs []int) int {
	minPrice := 0
	for i, n := range needs {
		minPrice += n * price[i]
	}

loop:
	for _, sp := range special {
		newNeeds := make([]int, len(needs))
		copy(newNeeds, needs)

		for i := range newNeeds {
			newNeeds[i] -= sp[i]
			if newNeeds[i] < 0 {
				continue loop
			}
		}
		curPrice := shoppingOffers(price, special, newNeeds) + sp[len(price)]
		if curPrice < minPrice {
			minPrice = curPrice
		}
	}
	return minPrice
}

func main() {
	price := []int{2, 5}
	special := [][]int{{3, 0, 5}, {1, 2, 10}}
	needs := []int{3, 2}
	print(shoppingOffers(price, special, needs))
}
